package pro.softzhang.algo.lc0;

import pro.softzhang.algo.common.ListNode;
import pro.softzhang.algo.common.Utils;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * 25 K个一组翻转链表
 * https://leetcode.cn/problems/reverse-nodes-in-k-group
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 */
public class LC25_ReverseNodesInKGroup {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
        Utils.printLinkedList(head);
        ListNode reversedHead = new Solution1().reverseKGroup(head, 2);
        Utils.printLinkedList(reversedHead);
    }

    /**
     *
     */
    @XOptimal
    static
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            // 0 求出链表长茺
            int len = 0;
            ListNode countPointer = head;
            while (countPointer != null) {
                len++;
                countPointer = countPointer.next;
            }

            ListNode dummy = new ListNode(-1, head),
                    rp = dummy, // 翻转点指针 reverse point
                    cur = head,
                    prev = null,
                    next;

            // 1 分组翻转
            while (len >= k) {
                len -= k;

                // 2 具体翻转
                // 2.1 具体翻转
                for (int i = 0; i < k; i++) {
                    next = cur.next;
                    cur.next = prev;
                    prev = cur;
                    cur = next;
                }

                // 2.2 链接起来
                next = rp.next;
                rp.next.next = cur;
                rp.next = prev;
                rp = next;
                // Utils.printLinkedList(dummy.next);
            }

            return dummy.next;
        }
    }

    static
    class Solution1 {
        public ListNode reverseKGroup(ListNode head, int k) {
            // 统计长度
           int len = 0;
           ListNode cp = head;
           while (cp != null) {
               len++;
               cp = cp.next;
           }

           // 所需指针变量
           ListNode dummy = new ListNode(Integer.MAX_VALUE, head),
                   rp = dummy,
                   cur = rp.next,
                   prev = null,
                   next;

           for(; k <= len; len-=k) {
               // 具体替换 循环k次
               for(int i = 0; i < k; i++) {
                   next = cur.next;
                   cur.next = prev;
                   prev = cur;
                   cur = next;
               }

               next = rp.next;
               rp.next.next = cur;
               rp.next = prev;
               rp = next;
           }

           return dummy.next;
        }
    }
}
